package ch04;

//连通分量
public class CC {
    private boolean[] marked;
    private int count;
    private int id[];
    public CC(Graph graph) {
        this.marked = new boolean[graph.V()];
        this.count = 0;
        this.id = new int[graph.V()];
        for (int s = 0; s < graph.V(); s++) {
            if (!marked[s]) {

                if (graph.adj(s).iterator().hasNext()) {
                    count++;
                }
                DFS(graph,s);
            }
        }
    }

    public void DFS(Graph graph, int v) {

        marked[v] = true;
        id[v] = count;
        for (Integer w : graph.adj(v)) {

            if(!marked[w])
                DFS(graph, w);

        }
    }

    public boolean connected(int a,int b)
    {

        return id[a] == id[b];
    }
    public int count(){
        return count;
    }

    public static void main(String[] args) {
        Graph graph = Graph.getGraphUseCase();
        CC cc = new CC(graph);
        System.out.println(cc.count);
        System.out.println(cc.connected(1,2));
        System.out.println(cc.connected(4,8));
        System.out.println(cc.connected(9,11));
        System.out.println(cc.connected(3,4));
        System.out.println(cc.connected(7,8));

        System.out.println(cc.count());
    }
}
